package skiplist;

import java.util.Random;

public class SkipList {
    public int level = 0;
    public SkipListNode top = null;

    public SkipList() {
        this(4);
    }

    //跳跃表的初始化
    public SkipList(int level) {
        this.level = level;
        SkipListNode skipListNode = null;

        SkipListNode temp = top;
        SkipListNode tempDown = null;
        SkipListNode tempNextDown = null;
        int tempLevel = level;
        while(tempLevel-- != 0){
            System.out.println("tempLevel:"+tempLevel);
            skipListNode = createNode(Integer.MIN_VALUE,tempLevel+1);
            temp = skipListNode;

            skipListNode = createNode(Integer.MAX_VALUE,tempLevel+1);
            temp.setNext(skipListNode);
            temp.setDownNext(tempDown);
            temp.getNext().setDownNext(tempNextDown);

            //临时节点
            tempDown = temp;
            tempNextDown = temp.getNext();
        }
        top = temp;
    }

    //创建一个节点
    private SkipListNode createNode(int value,int level){
        SkipListNode node =  new SkipListNode();
        node.setValue(value);
        node.setLevel(level);
        return node;
    }

/**
 * 关于这一点，跳跃表的设计者采用了抛硬币的策略，也就是通过概率的方式来计算新插入的节点应该向上构建多少层索引，
 * 或者有没有机会成为索引节点。因为抛硬币的结果只有正反各占50%，
 * 相当于这个节点每向上多构建一级或者有资格成为索引节点，层层都只有50%的概率，如下面的一段代码：
 *
 * 通过随机的奇偶数来模拟抛硬币的概率，如果遇到连续的偶数，就认为是向上跨级成功，但只要又一次出现奇数，就退出循环。
 * 奇数代表的是反面。反面就停止
 * 如果一个新增加的节点，第一次就遇到了反面，抱歉这个节点就不能成为索引节点，只能放在最底层的链表中
 */
//随机产生数k，k层下的都需要将值插入
public int randomLevel(){
    int k = 1;
    while(new Random().nextInt()%2 == 0){
        k ++;
    }
    return k > level ? level : k;
}

    /**
     * 算法实现思路：从顶层找，找到某个节点的下个节点把当前value大，就停止循环，让后当前节点往下找。
     *
     * @param value
     * @return
     */
    public SkipListNode find(int value){
     //从顶层找。一直找到最下面的一层元素，找不到返回空
        SkipListNode temp = top;
        while (true){
            //如果是小，代表最高一层，继续往下循环
            if(temp.getNext().getValue()< value){
                temp = temp.getNext();
            }else{
                //如果是第一层元素了，就返回自己
                if(temp.getDownNext() == null){
                    //返回要查找的节点的前一个节点
                    return temp;
                }
                //如果大了，往下循环
                temp = temp.getDownNext();
            }
        }
    }

}
